#include <stdlib.h>
#include <string.h>

#include "../include/sort.h"

int partition(void *data, int size, int esize, int idx_start, int idx_end, int (*compare)(const void *key1, const void *key2))
{
	void *flag, *tmp;
	char *src = data;

	flag = malloc(esize);
	if (!flag)
		return -1;
	tmp = malloc(esize);
	if (!tmp) {
		free(flag);
		return -1;
	}

	memcpy(flag, src + idx_end * esize, esize);

	while(1)
	{
		while(1)
		{
			if (compare(src + idx_start * esize, flag) < 0)
				idx_start++;
			else
				break;
		}

		while(1)
		{
			if (compare(src + idx_end * esize, flag) > 0)
				idx_end--;
			else
				break;
		}

		if (idx_start >= idx_end)
			return idx_end;

		memcpy(tmp, src + idx_start * esize, esize);
		memcpy(src + idx_start * esize, src + idx_end * esize, esize);
		memcpy(src + idx_end * esize, tmp, esize);

	}
}

int qksort(void * data, int size, int esize, int is, int ie, int(* compare)(const void * key1, const void * key2))
{
	int middle;
	if (is < ie)
	{
		middle = partition(data, size, esize, is, ie, compare);
		qksort(data, size, esize, is, middle - 1, compare);
		qksort(data, size, esize, middle + 1, ie, compare);
	}

	return 0;
}

